package Huffman;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class HuffmanTree<T> {
    public HuffmanNode<T> createTree(List<HuffmanNode<T>> nodes) {
        while (nodes.size() > 1) {
            Collections.sort(nodes);
            HuffmanNode<T> left = nodes.get(nodes.size() - 2);//令其左孩子的编码为0
            left.setCode("0");
            HuffmanNode<T> right = nodes.get(nodes.size() - 1);//令其右孩子的编码为1
            right.setCode("1");
            HuffmanNode<T> parent = new HuffmanNode<T>(null, left.getWeight() + right.getWeight());
            parent.setlChild(left);
            parent.setrChild(right);
            nodes.remove(left);
            nodes.remove(right);
            nodes.add(parent);
        }
        return nodes.get(0);
    }

    public List<HuffmanNode<T>> breath(HuffmanNode<T> root) {
        List<HuffmanNode<T>> list = new ArrayList<HuffmanNode<T>>();
        Queue<HuffmanNode<T>> queue = new LinkedList<>();
        if (root != null) {
            queue.offer(root);
            root.getlChild().setCode(root.getCode() + "0");
            root.getrChild().setCode(root.getCode() + "1");
        }

        while (!queue.isEmpty()) {
            list.add(queue.peek());
            HuffmanNode<T> node = queue.poll();
            if (node.getlChild() != null)
                node.getlChild().setCode(node.getCode() + "0");
            if (node.getrChild() != null)
                node.getrChild().setCode(node.getCode() + "1");
            if (node.getlChild() != null)
                queue.offer(node.getlChild());
            if (node.getrChild() != null)
                queue.offer(node.getrChild());

        }
        return list;
    }
}